package msb.class07;


import common.sort.AbstractSort;
import common.util.ArrayUtil;
import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

/**
 * 堆排序
 * 时间复杂度O(N*logN)
 * 额外空间复杂度O(1)
 * <p>
 * 大根堆
 */
public class Code01_heapSort extends AbstractSort {


    public static class Heap {
        public int heapSize;
        public int arr[];

        public Heap(int maxSize) {
            arr = new int[maxSize];
            heapSize = 0;
        }

        //处理成大根堆
        public Heap(int arr[]) {
            for (int i = arr.length - 1; i >= 0; i--) {
                heapify(arr, i, arr.length);
            }
            this.arr = arr;
            this.heapSize = arr.length;
        }

        public void add(int num) {
            if (heapSize == arr.length) {
                throw new RuntimeException();
            }
            arr[heapSize] = num;
            heapInsert(arr, heapSize);
            heapSize++;
        }

        public int peek() {
            if (heapSize == 0) {
                throw new RuntimeException();
            }
            int top = arr[0];
            arr[0] = arr[heapSize - 1];
            heapify(arr, 0, heapSize - 1);
            heapSize--;
            return top;
        }

        public void sort() {
            for (int i = heapSize - 1; i > 0; i--) {
                arr[i] = peek();
            }
        }
    }


    /**
     * 堆结构
     * index位置向上浮
     * 判断是否大于父节点，大于则交换
     */
    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[parent(index)]) {
            ArrayUtil.swap(arr, index, parent(index));
            index = parent(index);
        }
    }

    /**
     * 堆结构
     * index位置向下沉
     * 在小于heapSize的位置上，判断左右孩子，最大孩子大于自己，则交换
     */
    public static void heapify(int[] arr, int index, int heapSize) {
        while (leftChild(index) < heapSize) {
            int maxChild = rightChild(index) < heapSize ?
                    Math.max(arr[leftChild(index)], arr[rightChild(index)]) :
                    arr[leftChild(index)];
            int maxChildIndex = rightChild(index) < heapSize ?
                    arr[leftChild(index)] >= arr[rightChild(index)] ? leftChild(index) : rightChild(index) :
                    leftChild(index);
            if (maxChild > arr[index]) {
                ArrayUtil.swap(arr, index, maxChildIndex);
                index = maxChildIndex;
            } else {
                break;
            }
        }
    }


    /**
     * 堆结构父节点
     * 0的父节点也是0
     */
    public static int parent(int i) {
        return Math.max(((i + 1) / 2 - 1), 0);
    }

    public static int leftChild(int i) {
        return i * 2 + 1;
    }

    public static int rightChild(int i) {
        return i * 2 + 2;
    }

    @Test
    public void testParentAndChild() {
        Code01_heapSort code = new Code01_heapSort();
        Assert.assertEquals(0, code.parent(1));
        Assert.assertEquals(0, code.parent(2));
        Assert.assertEquals(1, code.parent(3));
        Assert.assertEquals(1, code.parent(4));
        Assert.assertEquals(2, code.parent(5));
        Assert.assertEquals(2, code.parent(6));


        Assert.assertEquals(1, code.leftChild(0));
        Assert.assertEquals(2, code.rightChild(0));
        Assert.assertEquals(3, code.leftChild(1));
        Assert.assertEquals(4, code.rightChild(1));
        Assert.assertEquals(5, code.leftChild(2));
        Assert.assertEquals(6, code.rightChild(2));

        System.out.println(code.parent(0));

    }

    @Override
    public void sort(int[] arr) {
        Heap heap = new Heap(arr);
        heap.sort();
    }

    @Test
    public void testSort() {
        check();
    }

    @Test
    public void testSortDebug() {
        int arr[] = new int[]{22, 50, 95};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }


}
